#include <iostream>
using namespace std;

const int N = 100010;

int e[N],ne[N],pre[N],h,id;
int mp[N];

// 头插
void push_front(int x)
{
    id++;
    e[id] = x;
    pre[id] = h;
    ne[id] = ne[h];
    pre[ne[h]] = id;
    ne[h] = id;
    mp[x] = id;
}

// 打印
void print()
{
    for(int i = ne[h];i;i = ne[i])
    {
        cout << e[i] << " ";
    }
    cout << endl << endl;
}

// 按值查找
int find(int x)
{
    // for(int i = ne[h];i;i = ne[i])
    // {
    //     if(e[i] == x) return i;
    // }
    return mp[x];
}

// 任意位置之后插入
void insert(int p,int x)
{
    id++;
    e[id] = x;
    pre[id] = p;
    ne[id] = ne[p];
    pre[ne[p]] = id;
    ne[p] = id;
    mp[x] = id;
}

// 任意位置之前插入
void insert_before(int p,int x)
{
    id++;
    e[id] = x;
    ne[id] = p;
    pre[id] = pre[p];
    ne[pre[p]] = id;
    pre[p] = id;
    mp[x] = id;
}

// 删除
void remove(int p)
{
    pre[ne[p]] = pre[p];
    ne[pre[p]] = ne[p];
    mp[e[p]] = 0;
}

int main()
{
    // 头插测试
    for(int i = 1;i <= 5;i++){
        push_front(i);
        print();
    }


    // 按值查找测试
    // cout << find(3) << endl << endl;   
    // cout << find(1) << endl << endl;

    // 任意位置插入测试 
    // insert(find(3),10);
    // print();
    // insert(find(1),11);
    // print();

    // 任意位置之前插入测试
    // insert_before(find(3),12);
    // print();
    // insert_before(find(5),13);
    // print();

    // 删除测试
    remove(find(3));
    print();
    remove(find(5));
    print();



    return 0;   
}
